package com.zjj.learn.algorithmPlus.segment1.recursion;

/**
 * 使用递归的思想实现插入排序
 *
 * @author zjj_admin
 * @date 2023/7/2 10:45
 */
public class InsertSort {


    /**
     * 插入排序
     *
     * @param a 排序数组 a
     */
    public static void sort(int[] a) {
        insert(a, 1);
    }

    /**
     * 插入排序的递归操作
     *
     * @param a
     * @param low 无序和有序的分界点
     */
    public static void insert(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        //插入操作
        int t = a[low];
        int i = low - 1;
        // 从当前位置一直向前遍历，只有遇到了比当前值大的数据就进行替换
        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = t;
        //递归插入
        insert(a, low + 1);
    }

}
